/*
* 1.左偏树/左式堆
    左偏树作为可并堆的一种数据结构，其重点在于将两个堆合并，
    在维护堆的性质之外，每个节点x另外维护一个信息dist[x]表示x到最近的叶子节点的距离
    且dist[l]>=dist[r]，从而保证合并复杂度O(logn) <- 根节点的距离<=logn


* 2.op
    (1) 插入一个数 O(logn)
    (2) 求最小值 O(1)
    (3) 删除最小值 O(logn)
    (4) 合并两棵树 O(logn)
        merge(a, b) 合并子树a,b，并返回合并后的根节点

* 本题:
    cost[i, j]: 将[i, j]变成单调序列的最小代价
    f(i, j): 将a[i]~a[i]分成j个单调区间的最小代价
    sum整个区间和 size整个区间数的个数 sum'较小一半数的和 size'较小一半数的个数 root左偏树根节点(中位数下标)
    区间最小代价 mid*size'-sum'+sum-sum'-(size-size')*mid

    dp
    f[i][j]=min(f[i-k][j-1]+cost[i-k+1][i]) k∈[1, i]
*/ 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define DEBUG
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输
const int N=1010;
int n, m;
int f[N][11], cost[N][N], w[N]; //w[]原始序列
//cost[i][j]: 将[i, j]变成单调序列的最小代价
//f[i][j]: 将a[i]~a[i]分成j个单调区间的最小代价
int val[N], l[N], r[N], dist[N];
struct Segment
{
    int root; //根节点(中位数下标) 大小
    int totSum, totCnt; //总的和、总的大小
    int treeSum, treeCnt; //较小一半的和、较小一半的大小

    int getCost()//计算当前区间的最小代价
    {
        int mid=val[root];
        return mid*treeCnt-treeSum+totSum-treeSum-mid*(totCnt-treeCnt);
    }
}stk[N]; int top;

int merge(int x, int y) //将x和y所在的左偏树合并，并返回根节点
{
    if(!x||!y) return x+y;
    if(val[x]<val[y]) swap(x, y); //y<x(权值或顺序)
    r[x]=merge(r[x], y);
    if(dist[l[x]]<dist[r[x]]) swap(l[x], r[x]);
    dist[x]=dist[r[x]]+1;
    return x;
}

int pop(int x) //将以x为根的左偏树的根节点删除
{
    return merge(l[x], r[x]);
}

void getCost(int u) //计算以u为左端点的所有区间的最小代价
{
    top=0;
    int res=0;
    for(int i=u; i<=n; i++)
    {
        auto cur=Segment({i, val[i], 1, val[i], 1});
        l[i]=r[i]=0, dist[i]=1;
        while(top && val[stk[top].root]>val[cur.root])
        {
            res-=stk[top].getCost(); //删除之前记录的代价
            bool ispop=cur.totCnt%2 && stk[top].totCnt%2; //合并后是否需要删除堆顶元素
            //更新信息
            cur.root=merge(cur.root, stk[top].root);
            cur.totCnt+=stk[top].totCnt;
            cur.totSum+=stk[top].totSum;
            cur.treeCnt+=stk[top].treeCnt;
            cur.treeSum+=stk[top].treeSum;

            if(ispop) //弹出堆顶元素
            {
                cur.treeCnt--;
                cur.treeSum-=val[cur.root];
                cur.root=pop(cur.root);
            }
            top--;
        }
        stk[++top]=cur;
        res+=cur.getCost();
        cost[u][i]=min(cost[u][i], res);
    }
}

void solve()
{
    // n=read(); m=read();
    for(int i=1; i<=n; i++) scanf("%d", &w[i]); //w[i]=read();

    memset(cost, 0x3f, sizeof cost);

    for(int i=1; i<=n; i++) val[i]=w[i]-i; //严格单调递增->非严格单调递增

    for(int i=1; i<=n; i++) getCost(i); //计算以i为左端点的所有递增区间的代价

    for(int i=1; i<=n; i++) val[i]=-w[i]-i; //数值取反，计算单调递减
    for(int i=1; i<=n; i++) getCost(i); //计算以i为左端点的所有递减区间的代价

    memset(f, 0x3f, sizeof f);
    f[0][0]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=1; k<=i; k++)
                f[i][j]=min(f[i][j], f[i-k][j-1]+cost[i-k+1][i]);

    printf("%d\n", f[n][m]); //write(f[n][m]); puts("");
}

// #undef DEBUG
signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    
    int T=1; //T=read();
    // while(T--)
    while(~scanf("%d %d", &n, &m), n||m)
    {
        solve();
    }
    return 0;
}